package 链表;

/**
 * Created by yang on 2016/8/24.
 */
public class LinkedListOperate {

    private ListNode listNode = null;

    public LinkedListOperate() {}

    public LinkedListOperate(ListNode listNode) {
        this.listNode = listNode;
    }

    /**
     * Traverse listNode use recursion
     * @param head
     */
    public void traverseOfRecursion(ListNode head) {

        if (head != null) {
            System.out.println(head.val);
            ListNode node = head.next;
            traverseOfRecursion(node);
        }
    }

    /**
     * insert node from head
     *
     * @param val
     * @return
     */
    public ListNode insertOfHead(int val) {

        // create node with 'val'
        ListNode nodeOftmp = new ListNode(val);

        if (listNode == null) {
            listNode = nodeOftmp;
        } else {
            // save node of head
            ListNode headOftmp = listNode;
            // insert node to head
            listNode = nodeOftmp;
            // recover node of remain
            listNode.next = headOftmp;
        }
        return listNode;
    }

    /**
     * Insert node from tail
     * @param val
     * @return
     */
    public ListNode insertOfTail(int val) {

        // create node with 'val'
        ListNode nodeOftmp = new ListNode(val);

        if (listNode == null) {
            listNode = nodeOftmp;
        } else {
            // either 'listNode' or 'nodeOftail' can affect the list
            ListNode nodeOftail = listNode;
            while (nodeOftail.next != null) {
                nodeOftail = nodeOftail.next;
            }

            // insert node in the next of the last node
            nodeOftail.next = nodeOftmp;
        }
        return listNode;
    }

    /**
     * Insert node at the specified index
     * @param val
     * @param index
     * @return
     */
    public ListNode insertOfIndex(int val, int index) {

        // affect the original list ready to insert
        // remain the head node of 'listNode'
        ListNode nodeOfindex = listNode;

        // save the subsequent node from index node
        ListNode nodeOftmp = null;

        // count number when traverse list
        int indexOftmp = 1;

        // find the location to insert
        while (nodeOfindex != null) {

            // find the index
            if (indexOftmp == index) {

                // 1. save subsequent node
                nodeOftmp = nodeOfindex.next;
                // 2. insert node
                nodeOfindex.next = new ListNode(val);
                // 3. recover subsequent node
                nodeOfindex.next.next = nodeOftmp;
                // 4. break
                break;
            }
            // else, find next
            nodeOfindex = nodeOfindex.next;
            indexOftmp++;
        }
        // return affected list
        return listNode;
    }

    /**
     * Delete node from head
     * @return
     */
    public ListNode deleteOfHead() {

        ListNode nodeOfDelete = listNode;

        if (listNode != null) {
            nodeOfDelete = nodeOfDelete.next;
        }

        return nodeOfDelete;
    }

    /**
     * Delete node from tail
     * @return
     */
    public ListNode deleteOfTail() {

        ListNode nodeOfDelete = listNode;

        if (nodeOfDelete.next == null) {
            return null;
        }

        while (nodeOfDelete.next.next != null) {
            nodeOfDelete = nodeOfDelete.next;
        }

        nodeOfDelete.next = null;

        return listNode;
    }

    /**
     * Delete node with specified index
     * @param index
     * @return
     */
    public ListNode deleteOfindex(int index) {

        ListNode nodeOfdelete = listNode;
        ListNode nodeOftmp = null;
        int nodeOfindex = 1;

        // delete the head node
        if (index == 0) {
            listNode = deleteOfHead();
            return listNode;
        }

        while (nodeOfdelete != null) {

            if (nodeOfindex == index) {

                // 保存需要删除节点的后续节点
                nodeOftmp = nodeOfdelete.next.next;
                // 删除节点
                nodeOfdelete.next = null;
                // 恢复节点
                nodeOfdelete.next = nodeOftmp;
                break;
            }
            nodeOfdelete = nodeOfdelete.next;
            nodeOfindex++;
        }

        return listNode;
    }
}
